
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
	<link rel=stylesheet href='include/hoj.css' type='text/css'>
</head>
<body>
<center>
<div style="width:90%; text-align:left">
<img src="image/logo.png"/>
</div>
<table width=96%> 
	<tr align="center" class='hd' valign="top">
				<th><a href="faqs.php">F.A.Qs</a></th>
		<th><a href="./bbs.php">Web Board</a></th>
		<th><a href="./">Home</a></th>
		<th><a href="./problemset.html">ProblemSet</a></th>
		<th><a href="./status.php">Status</a></th>
		<th><a href="./ranklist.php">Ranklist</a></th>
		<th><a href="./contest.php">Contest</a></th>
		<th><a href=loginpage.php>Login</a></th><th><a href=registerpage.php>Register</a></th>	</tr>
</table>
</center>
<center>
<div class="notice">
	<div>
		<B>Notice:</B>鉴于种种原因，本OJ自下周星期一（3月5号）开始不再全面开放，请各位做好善后事宜，谢谢合作。	</div>
</div>
</center>
</div>
<title>Problem 1580. -- [Usaco2009 Hol]Cattle Bruisers -- 衡阳八中OJ离线版-2012-02-29</title><center><h2>1580: [Usaco2009 Hol]Cattle Bruisers</h2><span class=green>Time Limit: </span>10 Sec&nbsp;&nbsp;<span class=green>Memory Limit: </span>64 MB<br><span class=green>Submit: </span>28&nbsp;&nbsp;<span class=green>Solved: </span>16<br>[<a href='submitpage.php?id=1580'>Submit</a>][<a href='problemstatus.php?id=1580'>Status</a>][<a href='bbs.php?id=1580'>Discuss</a>]</center><h2>Description</h2><div class=content>Canmuu is out for revenge after being utterly defeated by Bessie
in paintball and has challenged Bessie to a video game.

In this game, Bessie starts out at point (BX, BY) in the coordinate
grid (-1,000 <= BX <= 1,000; -1000 <= BY <= 1,000), and tries to
escape, starting at time 0. She moves continuously at a velocity
of (BVX, BVY) units/second (-100 <= BVX <= 100; -100 <= BVY <= 100).
Thus, at time 1 she will be at point (BX + BVX, BY + BVY); at time
1.5 she will be at (BX + 1.5*BVX, BY + 1.5*BVY).

Unfortunately, Canmuu has sent N (1 <= N <= 50,000) cattle bruisers
to pursue Bessie.  At time t=0, cattle bruiser i is at position
(X_i, Y_i) (-1,000 <= X_i <= 1,000; -1,000 <= Y_i <= 1,000) with
velocity (VX_i, VY_i) units/second (-1,000 <= VX_i <= 1,000; -1,000
<= VY_i <= 1,000).

Each cattle bruiser carries a "proximity" weapon to fire at Bessie;
the weapon can hurt Bessie when the cattle bruiser is no further
than R (1 <= R <= 2,500) units from her.

Bessie has a shield to protect herself from these attacks. However,
she does not want to waste any of her shield's power, so she would
like to know the maximum number of cattle bruisers within firing
range for any (potentially non-integer) time t >= 0.

In order to avoid precision errors with real numbers, it is guaranteed
that the answer produced will be the same whether the attack range
is decreased to R-0.0001 or increased to R+0.0001.

FEEDBACK: Your first 50  submissions for this problem will be run
on some of the official test data, and you will receive a summary
of the results.

</div><h2>Input</h2><div class=content>
* Line 1: Six space-separated integers: N, R, BX, BY, BVX, and BVY

* Lines 2..N+1: Line i+1 contains four space-separated integers: X_i,
        Y_i, VX_i, and VY_i

</div><h2>Output</h2><div class=content>
* Line 1: Print a single integer denoting the maximum number of cattle
        bruisers within attack range at any point in time.
</div><h2>Sample Input</h2>
			<div class=content><span class=sampledata><br />
3 1 0 0 0 2<br />
0 -3 0 4<br />
1 2 -1 1<br />
1 -2 2 -1<br />
<br />
INPUT DETAILS:<br />
<br />
Bessie starts at point (0, 0) and is moving at 2 units per second<br />
in the (positive) y-direction. There are 3 cattle bruisers, the<br />
first of which starts at point (0, -3) and travels 4 units per<br />
second in the y-direction. The maximum distance for a cattle bruiser<br />
to be in range of Bessie is 1 unit.<br />
<br />
</span></div><h2>Sample Output</h2>
			<div class=content><span class=sampledata><br />
2<br />
<br />
OUTPUT DETAILS:<br />
<br />
At time 1.5, Bessie is at point (0, 3), and the three bruisers are<br />
at points (0, 3), (-0.5, 3.5), and (4, -3.5). The first two cattle<br />
bruisers are within 1 unit of Bessie, while the third will never<br />
be within 1 unit of Bessie, so 2 is the most achievable.</span></div><h2>HINT</h2>
			<div class=content><p></p></div><h2>Source</h2>
			<div class=content><p><a href='problemset.html?search='></a></p></div><center>[<a href='submitpage.php?id=1580'>Submit</a>][<a href='problemstatus.php?id=1580'>Status</a>][<a href='bbs.php?id=1580'>Discuss</a>]</center>﻿<br>

<a href="./"><span class=red>HOME</span></a>
<a href="javascript:history.go(-1)"><span class=red>Back</span></a>

<hr>
<center>
	<div class="footer">
			<a href=setlang.php?lang=ko>한국어</a>&nbsp;
		<a href=setlang.php?lang=cn>中文</a>&nbsp;
		<a href=setlang.php?lang=fa>فارسی</a>&nbsp;
		<a href=setlang.php?lang=en>English</a>&nbsp;
		<a href=setlang.php?lang=th>ไทย</a>
	<br>		<div>版权所有 &copy;2008-2012 WaterPark Organization. | <script src="http://s21.cnzz.com/stat.php?id=2982771&web_id=2982771" language="JavaScript"></script>
</div>
		<div>Based on opensource project <a href="http://hustoj.googlecode.com">hustoj</a>.</div>
	</div>
</center>
</body>
</html>
